Hybrid control systems are control systems involving both computer hardware and software as wall as other types of hardware such as sensors. An aircraft engine controller, for example, takes inputs such as engine speed, temperature and pressure; processes this information; and them provides outputs for controlling the operation of the engine, such as a signal indicating that more or less fuel is required. It is necessary for such a control system to execute various steps at set frequencies and in a particular order. For example, the above control system might input a pressure value, carry out a first processing step on that pressure value and carry out a second processing step on the results of the first processing step, before finally outputting a command to the engine depending on the results of the processing steps. It might then be necessary to repeat this whole sequence at a regular fixed interval. The steps in this sequence must execute at the correct frequencies and in the correct order to ensure that the engine is controlled in the desired manner.
Before discussing the way in which the steps of such a sequence are controlled, it is helpful to define various terms which are used in relation to the control system software.
1. A task is a functional unit within the control software, this unit being responsible for a particular step in a sequence of steps. For instance a task might relate to the reading of a pressure value, or the processing of such a value once read.
2. Each task has attributes associated with it, including:
a) its deadline, which is the time within which the task must be completed; PA1 b) its priority, which defines when the task must be executed in relation to other tasks; PA1 c) its period, which is used in the conventional sense for a task having a particular frequency; and PA1 d) its jitter constraint, which determines the variation allowed from precise periodicity.
3. An ordered list of tasks to be executed is referred to as a transaction. Within the transaction, tasks may have precedence, ie task A must occur before task B. Further, the entire transaction may have a maximum end-to-end delay, within which time all tasks within the transaction must complete.
Currently, the processing of such tasks within safety critical control systems tends to be carried out using so-called `cyclic executives`. The cyclic executive invokes a series of tasks in a fixed order, then repeats this task list at a specific rate called its cycle, or its major cycle in the common situation in which all tasks do not execute at the same frequency. When the frequencies are not identical, the tasks list defines a sequence such that each task is repeated sufficiently often that its frequency requirement is met. In this case, the execution of each individual task or group of tasks with the same period is called a minor cycle, and the frequency of the major cycle will be set to the least common multiple of the frequencies of each task. See the Paper by C Douglass Locke `Software Architecture for Hard Real Time Applications: Cyclic Executives -v- Fixed Priority Executives`. Cyclic executive scheduling has certain drawbacks, most importantly that any changes to the system are very difficult to implement. For example, the addition of a further sensor to a control system might require modification of the whole processing arrangement (see the above Paper).
An alternative to the cyclic executive approach is that of using `fixed priority scheduling`, wherein tasks are executed in order of their priority. The normal approach for assigning priorities is referred to as the `deadline monotonic policy`. This involves assigning priorities such that highest priority is given to tasks with the shortest deadlines.
Fixed priority scheduling has not previously been used extensively in real systems. Although much academic work has been carried out, it has often been performed with a set of given deadlines. Priorities are then assigned according to these given deadlines, and the tasks are carried out in order of decreasing priority. This does not address the initial problem of assigning deadlines to tasks. This invention deals particularly with that problem.
A common approach to priority assignment is to make the deadline for a particular task equal to its period. Thus, if a task is required to execute every 50 ms, the fundamental deadline by which each invocation of the task must execute is the earliest time at which the next invocation of the task may commence execution. However, for a complex set of system requirements, this simple approach is insufficient because it is necessary to take into account at least the following factors: jitter constraints, when for some tasks only a limited variation from precise periodicity is allowed; precedence, when for example task B must execute after task A, even if its period is longer; and end-to-end transaction delay requirements, when the maximum permitted time within which all tasks with a particular transaction must execute is limited.